class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int, int>> badOranges;
        int row = grid.size(), col = grid[0].size();
        int time = 0, goodOrangesNum = 0;

        //先将所有的腐烂橘子存入队列
        //记录新鲜橘子的数量
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
            {
                if (grid[i][j] == 1)
                    goodOrangesNum++;
                else if (grid[i][j] == 2)
                    badOranges.push(make_pair(i, j));
            }
        
        //有新鲜橘子再bfs
        while (goodOrangesNum > 0 && !badOranges.empty())
        {
            time++;
            int badOrangesNums = badOranges.size();
            while (badOrangesNums--)
            {
                auto firstOrange = badOranges.front();
                int m = firstOrange.first, n = firstOrange.second;
                badOranges.pop();

                if (m > 0 && grid[m - 1][n] == 1)
                {
                    goodOrangesNum--;
                    grid[m - 1][n] = 2;
                    badOranges.push(make_pair(m - 1, n));
                }
                if (m < row - 1 && grid[m + 1][n] == 1)
                {
                    goodOrangesNum--;
                    grid[m +  1][n] = 2;
                    badOranges.push(make_pair(m + 1, n));
                }
                if (n > 0 && grid[m][n - 1] == 1)
                {
                    goodOrangesNum--;
                    grid[m][n - 1] = 2;
                    badOranges.push(make_pair(m, n - 1));
                }
                if (n < col - 1 && grid[m][n + 1] == 1)
                {
                    goodOrangesNum--;
                    grid[m][n + 1] = 2;
                    badOranges.push(make_pair(m, n + 1));
                }
            }
        }

        if (goodOrangesNum > 0)
            return -1;

        return time;
    }
};